11516 - WiFi/11516.cpp

   1 /*
   2   Problem: 11516 - WiFi
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6  */
   7
   8 using namespace std;
   9 #include <algorithm>
  10 #include <iostream>
  11 #include <iterator>
  12 #include <sstream>
  13 #include <fstream>
  14 #include <cassert>
  15 #include <climits>
  16 #include <cstdlib>
  17 #include <cstring>
  18 #include <string>
  19 #include <cstdio>
  20 #include <vector>
  21 #include <cmath>
  22 #include <queue>
  23 #include <deque>
  24 #include <stack>
  25 #include <map>
  26 #include <set>
  27
  28 #define D(x) cout << #x " is " << x << endl
  29
  30 const int N = 100005;
  31
  32 int h[N], n;
  33
  34 bool solvable(double d, int r){
  35   int i = 0;
  36   //D(d), D(r);
  37   for (double pivot = h[0] + d; r--; pivot = h[i] + d){
  38     //D(pivot);
  39     while (i < n && h[i] <= pivot + d){
  40       ++i;
  41       //D(i);
  42     }
  43     if (i == n)
  44       return true;
  45   }
  46   return false;
  47 }
  48
  49 int main(){
  50   int C;
  51   for (cin >> C; C--; ){
  52     int r;
  53     cin >> r >> n;
  54     for (int i=0; i<n; ++i)
  55       cin >> h[i];
  56
  57     sort(h, h+n);
  58     int low = 0, high = h[n-1] - h[0];
  59
  60     while (low < high){
  61       int mid = (low+high)/2;
  62       if (solvable(mid/2.0, r)){
  63         high = mid;
  64       }else{
  65         low = mid + 1;
  66       }
  67     }
  68
  69     printf("%.1lf\n", low/2.0);
  70   }
  71   return 0;
  72 }